class LinkList{
public:
  int val;
  LinkList *next;

  LinkList(){

    this->val = -1;
    this->next = nullptr;

  }

  LinkList(int val){

    this->val = val;
    this->next = nullptr;

  }

  LinkList(int val, LinkList *next){

    this->val = val;
    this->next = next;

  }

};

class MinStack{
private:
  LinkList *head;
  int size;
public:
  /** initialize your data structure here. */
  MinStack(){

    this->head = new LinkList(-1, nullptr);
    this->size = 0;

  }

  void push(int x){

    // 求最小值
    int m;
    if(this->size > 0){
      m = min(getMin(), x);
    }else{
      m = x;
    }

    // 头插法
    LinkList *p = new LinkList(x, this->head->next);
    this->head->next = p;

    p = new LinkList(m, this->head->next);
    this->head->next = p;

    p = nullptr;
    ++this->size;

  }

  void pop(){

    if(this->size == 0){
      return;
    }

    LinkList *p = this->head->next;
    this->head->next = p->next;
    delete p;
    p = this->head->next;
    this->head->next = p->next;
    delete p;
    p = nullptr;

    --size;

  }

  int top(){

    if(size == 0){
      return 0;
    }

    return this->head->next->next->val;

  }

  int getMin(){

    if(this->size > 0){
      return this->head->next->val;
    }

    return 0;

  }
};